import random
import C02E4 
import time

times=0

def sort(array):
    if len(array) == 1:
        return array
    #print('len==',len(array))
    mid=len(array)>>1
    a=sort(array[:mid])
    # b=a.copy()
    c=sort(array[mid:])

    j=0
    k=0
    for i in range(len(array)):
        #print('j==',j,'k==',k,array)
        #print('len(c)===',len(c))
        # global times
        # times+=1
        if k==len(c) or (j<len(a) and a[j]<c[k]) :
            array[i]=a[j]
            j=j+1
        else:
            array[i]=c[k]
            k=k+1
    return array

def sortMethod2(array,low,hi):
    if hi-low == 1:
        return 
    mid = (hi+low) >>1
    #print("low==",low,"hi==",hi,"mid==",mid)

    sortMethod2(array,low,mid)
    sortMethod2(array,mid,hi)

    b=array[low:mid]

    j=low
    k=mid

    for i in range(low,hi):
        if (k==hi) or (j<mid and b[j-low]<array[k] ):
            array[i]=b[j-low]
            j+=1
        elif j==mid:
            return array
        else:
            array[i]=array[k]
            k+=1
    return array
if __name__ == '__main__':
    testArray = []
    while len(testArray) < 400000:
        testArray.append(random.randint(0, 40000))
    
    testArray2=testArray.copy()
    startTime= time.time()
    
    #print("最终结果==", sort(testArray))
    sort(testArray)
    print("花费时间",time.time()-startTime)

    startTime= time.time()
    #print("最终结果==", sortMethod2(testArray2,0,len(testArray2)))
    sortMethod2(testArray2,0,len(testArray2))
    print("花费时间",time.time()-startTime)
    #print("用的次数",time)